// Selection.hpp, part of the GallionFightGame project
// copyright(2010) Nicolas Brunie
#include <glm/glm.hpp>
#include <glm/gtc/matrix_projection.hpp>
#include <glm/gtc/matrix_transform.hpp>
#include <iostream>
#include <vector>
#include <list>

#ifndef __SELECTION_HPP__
#define __SELECTION_HPP__

using namespace std;
using namespace glm;

class Selection {
	private:
		/** A selection is a polygon defined
		 * by its vertex list organized in a vector
		 * for commodity
		 */
		vector<vec2> m_vector; 
	public:
		Selection() { return; };
		Selection(list<vec2> list_) {
			list<vec2>::iterator it;
			for (it = list_.begin(); it != list_.end(); it++) 
				m_vector.push_back(*it);
		};
		vector<vec2> getVector() { return m_vector; };
		void print() { 
			cout << "sel : ";
			for (unsigned int i = 0; i < m_vector.size();i++) cout << m_vector[i].x << "," << m_vector[i].y << " | " << endl;
			cout << endl;
		};

		/** does the arg point is within the selection ? */
		bool intersect(vec2 point) {
			// to determine whether or not a point
			// is inside the polygon, we have to verify each 
			// linear constraint implies by each edge 
			for (unsigned int i = 0; i < m_vector.size(); i++) {
				if (!verifyConstraint(i, point)) return false;
			}
			return true;
		};

		/* does the arg point verify the i th constraint : (>= in space) */
		bool verifyConstraint(int i, vec2 point) {
			vec2 p1 = m_vector[i];
			vec2 p2 = m_vector[(i+1) % m_vector.size()];
			if (p1.x == point.x and p1.y == point.y) return false;
			float coeff = (p2.y - p1.y) / (p2.x - p1.x);
			// and the constraint	
			float yx = (p1.y + coeff * (point.x - p1.x));
			if (p1.x < p2.x) return  yx < point.y; 
			else return yx > point.y;
		};

		/** add a point to the convex envelopp of selection */
		void addPoint(vec2 point) {
			// if point is inside the selection, we do nothing
			int size = m_vector.size();
			// if there is only 0 or 1 points
			if (size <= 1) { m_vector.push_back(point); return; }
			else if (size == 2) { 
				vec2 p1 = m_vector[0];
				vec2 p3 = m_vector[1];
				m_vector.push_back(p3);
				m_vector[1] = point;
				vec3 v1 = vec3(point - p1,0.0);
				vec3 v2 = vec3(p3 - p1,0.0);
				vec3 c = cross(v2,v1);
				if (c.z < 0.0) { m_vector[1] = p3; m_vector[2] = point;};
				return;
			};
			if (intersect(point)) {
				// cout << "point dans le polygone" << endl;
				return;
			};
			for (int i = 0; i < size; i++) {
				if (!verifyConstraint(i,point)) {
					// cout << "contrainte " << i << " non vérifiée" << endl;
					int d,f;
					d = i;
					f = (i+1) % size;
					while (f != d and !verifyConstraint(f,point)) f = (f+1) % size;
					// cout << "f final : " << f << endl;
					if (f == d) return;
					while (d != f and !verifyConstraint((d - 1 + size) % size,point)) d = (d - 1 + size) % size;
					// cout << "d final : " << d << endl;
					// if the next contraint is not verified we replace the middle point
					if ((f-d + size) % size != 1) {
						//m_vector[(i+1) % size] = point;
						vector<vec2> tmp;
						for (int j = f; j !=d;) {
							tmp.push_back(m_vector[j]);
							j = (j+1) % size;
						};
						tmp.push_back(m_vector[d]);
						tmp.push_back(point);
						m_vector = tmp;
						return;
					} else {
						// else we insert the point between i and i+1
						m_vector.push_back(m_vector[size - 1]);
						for (int j = size - 1; j > i+1; j--) m_vector[j] = m_vector[j-1];
						m_vector[i+1] = point; 
						return;
					};
				}
			};
		};
		void fusion(Selection* selection_) {
			// function to fusion this with parameter selection
		};
};


#endif
